'''
https://leetcode.cn/problems/walls-and-gates
'''
from collections import deque
from typing import List


class Solution:
    # bfs
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        """
        Do not return anything, modify rooms in-place instead.
        """
        m, n = len(rooms), len(rooms[0])
        q = deque()
        for i in range(m):
            for j in range(n):
                if rooms[i][j] == 0:
                    q.append((i, j))
        step = 0
        visited = [[False] * n for _ in range(m)]
        while q:
            for _ in range(len(q)):
                i, j = q.popleft()
                if visited[i][j]:
                    continue
                visited[i][j] = True
                rooms[i][j] = step
                for tx, ty in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                    if 0<=tx<m and 0<=ty<n and rooms[tx][ty] != -1:
                        q.append((tx, ty))
            step += 1

    # dfs
    def wallsAndGates2(self, rooms: List[List[int]]) -> None:
        """
        Do not return anything, modify rooms in-place instead.
        """
        m, n = len(rooms), len(rooms[0])
        def dfs(i, j, step):
            if i < 0 or j < 0 or i >= m or j >= n:
                return
            # 剪枝，入口不要剪掉
            if step and rooms[i][j] <= step:
                return
            rooms[i][j] = step
            for tx, ty in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):
                dfs(tx, ty, step+1)

        for i in range(m):
            for j in range(n):
                if rooms[i][j] == 0:
                    dfs(i, j, 0)

